/**
 * This file is part of Sonedyan.
 * 
 * Sonedyan is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation;
 * either version 3 of the License, or (at your option) any
 * later version.
 *
 * Sonedyan is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public
 * License along with Octave; see the file COPYING.  If not
 * see <http://www.gnu.org/licenses/>.
 * 
 * Copyright (C) 2009-2013 Jimmy Dubuisson <jimmy.dubuisson@gmail.com>
 */

package org.unige.mpej.eckmann.sonedyan.mr;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Stack;

import org.apache.log4j.Logger;

public class TarjanAlgo
{
	private static Logger log = Logger.getLogger(org.unige.mpej.eckmann.sonedyan.mr.TarjanAlgo.class);
	
	private static final int MIN_COMPONENT_SIZE = 100000;
	
	/**
	 * vertex indices
	 */
	private class Vertex
	{
		public int index;
		public int lowLink;
		
		public Vertex(int index, int lowLink)
		{
			this.index = index;
			this.lowLink = lowLink;
		}
		
		public boolean equalIndices()
		{
			return (this.index == this.lowLink);
		}
	}
	
	private class CStack<E>
	{
		private Stack<E> S;
		private HashMap<E, Integer> H;
		
		public CStack(int capacity)
		{
			this.S = new Stack<E>();
			this.H = new HashMap<E, Integer>(capacity);
		}
		
		public void push(E e)
		{
			this.S.push(e);
			
			Integer c = this.H.get(e);
			
			if (c == null)
				this.H.put(e,1);
			else
				this.H.put(e, c+1);
		}
		
		public E pop()
		{
			E e = this.S.pop();
			
			Integer c = this.H.get(e);
			
			if (c == 1)
				this.H.put(e, null);
			else
				this.H.put(e, c-1);
			
			return e;
		}
		
		public boolean contains(E e)
		{
			return this.H.containsKey(e);
		}
	}
	
	private LocalGraphLoader loader;
	private CStack<Integer> S;
	private int index;
	private HashMap<Integer, Vertex> vertices;
	// private ArrayList<ArrayList<Integer>> components;
	private BufferedWriter bw;
	private int maxSize;
	
	
	/**
	 * constructor
	 */
	public TarjanAlgo(LocalGraphLoader loader, BufferedWriter bw)
	{
		this.loader = loader;
		
		this.index = 0;
		// this.S = new Stack<Integer>();
		this.S = new CStack<Integer>(LocalGraphLoader.TWITTER_INDEX_SIZE);
		
		this.vertices = new HashMap<Integer, Vertex>(LocalGraphLoader.TWITTER_INDEX_SIZE);
		// this.components = new ArrayList<ArrayList<Integer>>();
		this.bw = bw;
		this.maxSize = 0;
	}
	
	/**
	 * get the strongly connected components
	 */
	public void getStronglyConnectedComponents()
	{
		for (int u: loader.nextVertex.keySet())
		{
			if (this.vertices.get(u) == null)
			{
				this.strongConnect(u);
			}
		}
		
		log.info("Giant component has size: " + this.maxSize);
	}
	
	/*
	 * get the strongly connected component vertex u belongs to
	 */
	private void strongConnect(int u)
	{
		// set the depth index for u to the smallest unused index
		Vertex uData = new Vertex(this.index, this.index);
		this.vertices.put(u, uData);
		
		this.index++;
		this.S.push(u);
		
		// consider successors of v
		ArrayList<Integer> children = this.loader.getChildren(u);
		
		for (int v: children)
		{	
			if (this.vertices.get(v) == null)
			{
				// recursive call
				this.strongConnect(v);
				
				uData.lowLink = Math.min(uData.lowLink, this.vertices.get(v).lowLink);
				this.vertices.put(u, uData);
			}
			else if (this.S.contains(v))
			{
				uData.lowLink = Math.min(uData.lowLink, this.vertices.get(v).index);
				this.vertices.put(u, uData);
			}
		}
		
		if (uData.equalIndices())
		{
			ArrayList<Integer> component = new ArrayList<Integer>();
			
			int i;
			
			do
			{
				i = this.S.pop();
				component.add(i);
			} while(i != u);
			
			int size = component.size();
			log.info("Found component of size: " + size + " (index: " + this.index + ")");
			
			if (size > MIN_COMPONENT_SIZE)
			{
				if (size > this.maxSize)
					this.maxSize = size;
				this.writeComponent(component);
			}
		}
	}
	
	/**
	 * write component to the specified writer
	 */
	private boolean writeComponent(ArrayList<Integer> component)
	{
		try
		{
			this.bw.write("Component size: " + component.size() + "\n");
			
			for (int c:component)
			{
				bw.write(c + ",");
			}
			
			this.bw.write("\n");
			
			return true;
		}
		catch(IOException e)
		{
			log.error("Unable to write component: " + e.getMessage());
			return false;
		}
	}
	
	/**
	 * main method
	 */
	public static void main(final String[] args) throws Exception
	{
		LocalGraphLoader loader = new LocalGraphLoader();
		BufferedWriter bw = new BufferedWriter(new FileWriter("twitter-sccs.txt"));

		TarjanAlgo tarjan = new TarjanAlgo(loader,bw);
		
		tarjan.getStronglyConnectedComponents();
		
		bw.close();
	}

}
